Skip to main content

Graph Valid Tree

Question​

Given a directed graph, determine if it is a valid tree (contains no cycles and is connected).

Example 1
Input: n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Solution​

all//Graph Valid Tree.py


def valid_tree(n, edges):
    # Create an adjacency list representation of the graph
    graph = [[] for _ in range(n)]
    for v, w in edges:
        graph[v].append(w)
        graph[w].append(v)

    # Perform a BFS to ensure the graph is connected
    visited = [False] * n
    queue = [0]
    while queue:
        v = queue.pop(0)
        visited[v] = True
        for w in graph[v]:
            if visited[w] == False:
                queue.append(w)

    # Check if all nodes have been visited
    if all(visited):
        # Check if the graph has any cycles
        edges_remaining = len(edges)
        for v in range(n):
            edges_remaining -= len(graph[v])

        if edges_remaining == 0:
            return True
    return False